package com.example.bst;

/**
 * @Date 2022/4/5
 * @Created by Jonathan
 */
public class BSTWithParentPointer {

    /*
     * 二叉树的结构定义如下：
     * Class Node{
     *      V value;
     *      Node left;
     *      Node right;
     *      Node parent;
     * }
     * 给你二叉树中的某个节点 返回该节点的后继节点
     * 解释：后继节点是指中序遍历的后面一个节点
     */


    static class Node {
        Integer value;
        Node right;
        Node left;
        Node parent;
    }

    /**
     * 找二叉树的后继节点
     * 1) 有右子树的时候 找到右子树的最左的节点即可
     * 2) 当前节点是父节点的右孩子的时候 向上遍历
     * 当不满足条件退出的时候 这个父节点就是当初节点的后继节点
     */
    public Node getSuccessorNode(Node node) {
        // 判空
        if (node == null) return null;
        // 有右子树
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            // 无右子树
            Node parent = node.parent;
            while (parent != null && parent.right == node) { // 当前节点是其父节点的右孩子
                node = parent;
                parent = node.parent;
            }
            // 推出while循环的时候  当前节点是父节点的左孩子   此时这个父节点就是当初节点的后继节点
            return parent;
        }
    }

    /**
     * 找二叉树最左边的节点
     */
    private Node getLeftMost(Node node) {
        if (node == null) return node;
        while (node.left != null)
            node = node.left;
        return node;
    }

}
